package main

type Node struct {
	key   int
	value int
	next  *Node
	prev  *Node
}

type LRUCache struct {
	m        map[int]*Node
	head     *Node
	tail     *Node
	capacity int
	size     int
}

func Constructor(capacity int) LRUCache {
	return LRUCache{
		m:        make(map[int]*Node),
		head:     nil,
		tail:     nil,
		capacity: capacity,
		size:     0,
	}
}

// insert in head
func (this *LRUCache) pushLink(node *Node) {
	if this.head == nil {
		this.head = node
		this.tail = node
	} else {
		node.next = this.head
		this.head.prev = node
		this.head = node
	}
}

func (this *LRUCache) removeLast() *Node {
	if this.tail == nil {
		// empty list
		return nil
	}
	n := this.tail
	this.removeLink(n)
	return n
}

func (this *LRUCache) removeLink(node *Node) {
	if node.prev == nil {
		this.head = node.next
	} else {
		node.prev.next = node.next
	}
	if node.next == nil {
		this.tail = node.prev
	} else {
		node.next.prev = node.prev
	}
}

func (this *LRUCache) Put(key int, value int) {
	node, ok := this.m[key]
	if ok {
		// existed
		this.removeLink(node) // remove old position in link
	} else {
		// new
		this.size++
	}
	node = &Node{key: key, value: value}
	this.pushLink(node)
	this.m[key] = node

	if this.size > this.capacity {
		n := this.removeLast()
		if n != nil {
			delete(this.m, n.key)
		}
		this.size--

	}
}

func (this *LRUCache) Get(key int) int {
	node, ok := this.m[key]
	if !ok {
		return -1
	}
	this.removeLink(node)
	node.next = nil
	node.prev = nil
	this.pushLink(node)
	return node.value
}

func main() {
	cache := Constructor(2)
	cache.Put(1, 1)
	cache.Put(2, 2)
	println(cache.Get(1)) // 返回  1
	cache.Put(3, 3)       // 该操作会使得密钥 2 作废
	println(cache.Get(2)) // 返回 -1 (未找到)
	cache.Put(4, 4)       // 该操作会使得密钥 1 作废
	println(cache.Get(1)) // 返回 -1 (未找到)
	println(cache.Get(3)) // 返回  3
	println(cache.Get(4)) // 返回  4

}
